"""
题目背景：

    在进行复杂的科学计算或模拟时，经常会遇到一个函数被同样参数反复调用的情况，例如在递归求解问题时。为了避免重复计算、提升程序效率，我们可以使用“备忘录”技术。
    请你实现一个装饰器来为函数提供这种缓存功能，并将其应用于一个动态规划问题中。

题目描述：

    假设一个智能机器人在一个 m×n 的网格上移动，它只能向右或向下移动。机器人从左上角（位置 (0, 0)）出发，需要到达右下角（位置 (m-1, n-1)）。请计算从起点到终点共有多少条不同的路径。

你需要：

    1.实现一个名为 memoize 的装饰器，该装饰器可以缓存任何函数的计算结果。当函数以相同的参数再次被调用时，直接返回缓存中的结果，而不是重新计算。

    2.编写一个递归函数 count_paths(m, n) 来计算路径数量，并使用你实现的 @memoize 装饰器来对其进行优化。

测试用例：

输入 (m, n)	    预期输出
(1, 1)	        1
(1, 5)	        1
(5, 1)	        1
(2, 2)	        2
(3, 2)	        3
(2, 3)	        3
(3, 3)	        6
(3, 7)	        28
(7, 3)	        28
(10, 10)	    48620
(18, 18)	    2333606220



"""

"""
实现代码总结(非题目要求)：
memoize 装饰器：
    使用字典cache存储函数调用结果，键为函数参数的元组（确保可哈希），值为计算结果
    调用函数时先检查缓存，若存在则直接返回，否则计算后存入缓存
    使用functools.wraps保留原函数的元信息（如函数名、文档字符串）
count_paths 函数：
    递归逻辑：到达(m,n)的路径数 = 到达上方(m-1,n)的路径数 + 到达左方(m,n-1)的路径数
    基线条件：1x1网格只有1条路径
    边界条件：单行或单列网格只有 1 条路径（只能沿一个方向移动）
    通过@memoize装饰器缓存结果，避免重复计算，大幅提升效率
"""

# 从functools模块导入wraps工具，用于保留被装饰函数的原始信息（如函数名、注释等）
from functools import wraps


# 实现memoize装饰器 用于缓存函数的计算结果，避免重复计算
# 这是装饰器的核心入口，装饰器的作用是 “包装” 目标函数，在不修改其源码的情况下添加额外功能（这里是缓存）。
def memoize(func):
    #print("memoize函数被调用...")
    # 创建一个空字典作为缓存容器，键是函数参数（元组形式），值是对应参数的计算结果
    # 由于 cache 定义在 memoize 内部，且被内部的 wrapper 函数引用，它会形成 “闭包”，生命周期与装饰后的函数绑定（缓存会一直保留，直到程序结束或手动清除）。
    cache = {}
    # 定义一个包装函数wrapper，它最终会替代原函数被调用
    # *args表示接收任意数量的位置参数（比如(m,n)会被打包成元组传入）
    # @wraps(func)：这是 functools.wraps 装饰器（需要提前导入 from functools import wraps），作用是保留被装饰函数的元信息（如函数名、文档字符串等）。
    # 如果没有这一行，当我们查看装饰后函数的 __name__ 或 __doc__ 时，会显示 wrapper 而非原函数名，可能导致调试 confusion。
    #当在函数定义中使用 *args 时，*是特殊语法，作用是将传入的多个位置参数 “打包” 成一个元组（tuple），并赋值给变量 args; *args表示不管调用时传入多少个位置参数，都把它们打包成一个元组给 args
    @wraps(func)  # 保留原函数的元信息
    def wrapper(*args):  # 定义一个内部包装函数 wrapper，它会替代原函数被调用（即装饰后，调用原函数最终实际执行的是 wrapper）。
        #print("wrapper函数被调用...")
        # 将传入的参数转换为元组作为缓存的键（因为列表等不可哈希的类型不能作为字典键，而元组可以）
        # 这里args本身就是元组（比如调用count_paths(3,2)时，args就是(3,2)）
        # 将接收的参数 args（本身就是元组）直接作为缓存的键 key。
        # 原因：字典的键必须是 “可哈希” 类型，而元组（元素不可变时）是可哈希的，适合作为键；如果用列表等不可哈希类型则会报错。
        key = args
        # 检查缓存中是否已经有这个参数对应的结果
        if key not in cache:
            # 如果缓存中没有，就调用原函数计算结果，并把结果存入缓存
            cache[key] = func(*args)
        ##返回对应的结果
        return cache[key]

    # 装饰器返回包装函数wrapper，后续调用原函数时，实际执行的是wrapper;  这意味着：当用 @memoize 装饰某个函数后，该函数名实际指向的是 wrapper 函数，后续调用时会触发缓存逻辑。
    return wrapper


# 编写递归函数count_paths，并用@memoize装饰器优化
# 机器人只能向右或向下走，所以到(m,n)的路径数 = 到上方(m-1,n)的路径数 + 到左方(m,n-1)的路径数。
@memoize
def count_paths(m, n):
    #print("count_paths函数被调用...")
    #计算m×n网格中从(0,0)到(m-1,n-1)的不同路径数（只能向右或向下移动）
    # 基线条件：当网格为1x1时，只有1条路径
    if m == 1 and n == 1:
        return 1
    # 基线条件2：如果是单行（m=1）或单列（n=1）的网格，只有1条路径；单行只能一直向右走，单列只能一直向下走
    if m == 1 or n == 1:
        return 1
    # 递归逻辑：到达(m,n)的路径数 = 到达上方格子(m-1,n)的路径数 + 到达左方格子(m,n-1)的路径数
    # 因为机器人只能向下或向右移动，所以最后一步要么是从上方下来，要么是从左方过来
    return count_paths(m - 1, n) + count_paths(m, n - 1)


# 测试用例验证
if __name__ == "__main__":
    # 定义测试用例：每个元素是((m, n), 预期结果)
    test_cases = [
        ((1, 1), 1),
        ((1, 5), 1),
        ((5, 1), 1),
        ((2, 2), 2),
        ((3, 2), 3),
        ((2, 3), 3),
        ((3, 3), 6),
        ((3, 7), 28),
        ((7, 3), 28),
        ((10, 10), 48620),
        ((18, 18), 2333606220)
    ]

    for (m, n), expected in test_cases:
        result = count_paths(m, n)
        assert result == expected, f"测试用例({m}, {n})失败：预期正确答案:{expected}，实际执行出:{result}"



    print("所有测试用例通过！")



"""
带有装饰器的代码，如本例所示，执行顺序(见本例的3处print语句(已经注释掉))

三处print语句的执行顺序为：
memoize函数被调用... → wrapper函数被调用... → count_paths函数被调用...

原因分析：
这是由装饰器的执行机制决定的，具体步骤如下：
1：定义装饰器时，memoize函数先被调用  当代码执行到@memoize时（装饰器语法），Python 会先执行memoize函数本身，因此第一句print("memoize函数被调用...")会先触发。此时memoize函数的作用是创建并返回wrapper函数（装饰器的核心逻辑），但wrapper此时还未被执行。
2：调用被装饰的count_paths时，wrapper函数被触发  当后续代码中调用count_paths(m, n)时，由于函数已被@memoize装饰，实际执行的是memoize返回的wrapper函数。因此wrapper内部的print("wrapper函数被调用...")会被执行。
3：....... 因此count_paths内部的print("count_paths函数被调用...")最后执行。


总结：
装饰器的执行流程是：
定义装饰器时先执行装饰器本身 → 调用被装饰函数时执行wrapper → wrapper内部再调用原函数，因此三处 print 的顺序按上述逻辑依次触发。


"""


"""
这道题既可以用递归解决，也涉及动态规划的思想，两者并不矛盾，具体可以从以下角度理解：
1. 递归是实现方式
题目要求编写 count_paths(m, n) 函数，其核心逻辑是递归：
    递归的思路：到达 (m, n) 的路径数 = 到达上方 (m-1, n) 的路径数 + 到达左方 (m, n-1) 的路径数（因为只能向右或向下移动）。
    递归的终止条件：当 m=1 或 n=1 时（单行或单列），只有 1 条路径；当 m=1 且 n=1 时（起点即终点），也只有 1 条路径。
    
2. 动态规划的核心是 “避免重复计算”
动态规划的本质是通过缓存中间结果，避免重复计算，从而优化效率。本题中：
    未优化的递归会存在大量重复计算（例如计算 count_paths(3,3) 时，count_paths(2,2) 会被计算多次）。
    题目要求实现的 @memoize 装饰器，正是动态规划中 “备忘录法”（一种递归形式的动态规划）的体现：通过缓存已计算的 (m, n) 对应的路径数，后续遇到相同参数时直接返回缓存结果，避免重复计算。

结论
这道题是用递归实现，并结合动态规划（备忘录法）优化的问题。递归是解决问题的 “步骤逻辑”，动态规划（缓存）是提升效率的 “优化手段”，两者结合完成了题目要求。
"""
